#pragma once
#include<iostream>
#include<vector>
using namespace std;

template<class K>
struct Hash_Link
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

template<>
struct Hash_Link<string>
{
    size_t operator()(const string& s)
    {
        // BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};

template<class K,class V>
struct ListNode
{
    pair<K, V> kv;
    ListNode* next;

    ListNode(const pair<K,V>& k)
        :kv(k),next(nullptr)
    {}
    ListNode()
        :next(nullptr)
    {}
};

template<class K,class V,class HashFunc = Hash_Link<K>>
class LinkHash
{
public:
    LinkHash()
        :n(0)
    {}
    ~LinkHash()
    {}
    ListNode<K,V>* find(const K& key)
    {
        if (tables.size() == 0)
            return nullptr;
        size_t index = HashFunc()(key) % tables.size();
        ListNode<K, V>* cur = tables[index];
        while (cur)
        {
            if (cur->kv.first == key)
            {
                return cur;
            }
            cur = cur->next;
        }
        return nullptr;
    }
    bool Insert(const pair<K, V>& kv)
    {
        ListNode<K, V>* ret = find(kv.first);
        if (ret != nullptr)
            return false;
        //判断是否需要增容
        if (tables.size() == 0 || n / tables.size() == 1 )
        {
            vector<ListNode<K, V>*> newTables;
            newTables.resize(tables.size() == 0 ? 10 : tables.size() * 2);
            
            for (int i = 0; i < tables.size(); i++)
            {
                ListNode<K, V>* cur = tables[i];
                while (cur)
                {
                    ListNode<K, V>* next = cur->next;
                    cur->next = newTables[i];
                    newTables[i] = cur;
                    cur = next;
                }
                tables[i] = nullptr;//!!!
            }
            tables.swap(newTables);
        }
        HashFunc hf;
        size_t index = hf(kv.first) % tables.size();
        ListNode<K, V>* newnode = new ListNode<K, V>(kv);
        newnode->next = tables[index];
        tables[index] = newnode;
        n++;
        return true;
    }
    bool erase(const K& key)
    {
        HashFunc hf;
        size_t index = hf(key) % tables.size();
        ListNode<K, V>* cur = tables[index];
        ListNode<K, V>* prev = nullptr;
        while (cur)
        {
            if (cur->kv.first == key)
            {
                if (prev == nullptr)//要删的是头结点
                {
                    tables[index] = cur->next;//换头
                }
                else
                {
                    prev->next = cur->next;
                }
                n--;
                delete cur;
                return true;
            }
            else
            {
                prev = cur;
                cur = cur->next;
            }
        }
        return false;
    }

    void Print()
    {
        for (int i = 0; i < tables.size(); i++)
        {
            cout << "当前所在的桶号为：" << i << " ";
            ListNode<K, V>* cur = tables[i];
            cout << "所含元素为：";
            while (cur)
            {
                cout << cur->kv.first << " ";
                cur = cur->next;
            }
            cout << endl;
        }
    }
private:
    vector<ListNode<K, V>*>  tables;
    size_t n = 0;//给缺省值
};